package com.example.algorithm.tree;

// 本案例演示的是，手撕二叉树深度。
public class BinaryTreeDepth {

    public static void main(String[] args) {
        // 创建一个二叉树
        // 就是一个普通的二叉树而已。没有什么顺序。
        //    3
        //9       20
        //    15       7
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);

        int depth = maxDepth(root);
        System.out.println("二叉树的深度是：" + depth);
    }

    public static int maxDepth(TreeNode root) {
        // 根节点都为0，那自然就是树的深度为空喽。
        // 后续不断地把节点传入maxDepth，总会有一层左右子节点为null的。所以，这个也是递归方法的结束条件。不然就无限递归了。
        if (root == null) {
            return 0;
        }

        // 对树的根节点的左节点递归使用maxDepth方法
        int left = maxDepth(root.left);
        // 对树的根节点的左节点递归使用maxDepth方法
        int right = maxDepth(root.right);

        // 取左右子节点的较大者，就为递归的深度。
        int bigger = Math.max(left, right);

        // 因为bigger仅仅是各层节点的子树的深度，所以，最终递归方法返回的值，总是要加1的。
        // 过了上面的递归截胡点之后，走到这里，其实就是从递归最内层一层一层往递归最外层返回，那么当然就是返回一层，就加1
        return bigger + 1;
    }
}
